black = 0
red   = 1

is_black = lambda n: n==None or n.color==black
is_red   = lambda n: n!=None and n.color==red

all_nodes = []

class rbnode:
    def __init__(self, value, color=red,idx=0):
        all_nodes.append(self)
        self.value = value
        self.color = color
        self.dire  = 0
        self.idx   = idx
        self.parent = None
        self.child  = [None, None]

    def __getitem__(self, dire):
        return self.child[dire]

    def __setitem__(self, dire, y):
        self.child[dire] = y
        if y!= None:
            y.parent = self
            y.dire   = dire

    def sibling(self):
        return self.parent[1-self.dire]
    
    def gparent(self):
        return self.parent.parent
    
    def uncle(self):
        return self.parent.sibling()

    def root(self):
        node = self
        while node.parent != None:
            node = node.parent
        return node

    def rotate(self, dire):
        child = self[1-dire]
        gchild = child[dire]
        if gchild != None:
            gchild.idx += child.idx
        child.idx += self.idx
        self.idx -= child.idx
        if self.parent == None:
            child.parent=None
        else:
            self.parent[self.dire] = child
        self[1-dire] = gchild
        child[dire] = self

    def find(self,value):
        node = self
        while node.value != value:
            idx = 0 if value < node.value else 1
            if node[idx] == None:
                return idx, node
            node = node[idx]
        return 'found', node

    def get(self, idx):
        node = self
        while node.idx != idx:
            #print (node.value, idx)
            _idx = 0 if idx < node.idx else 1
            if node[_idx]==None:
                return None
            idx -= node.idx
            node = node[_idx]
        return node

    def insert(self, value):
        idx, node = self.find(value)
        if idx == 'found':
            return self
        node[idx] = rbnode(value,idx=idx)
        _node = node = node[idx]
        while node.parent != None:
            if node.dire == 0:
                node.idx -= 1
                node.parent.idx += 1
            node = node.parent
        node = _node
        while True:
            if node.parent == None:
                node.color = black
                break
            if node.parent.color==black:
                break
            if is_red(node.uncle()):
                node.uncle().color = black
                node.parent.color  = black
                node.gparent().color = red
                node = node.gparent()
                continue
            if node.dire != node.parent.dire:
                node=node.parent
                node.rotate(node.dire)
            node.parent.color = black
            node.gparent().color = red
            node.gparent().rotate(1-node.dire)
            break
        return self.root()
    
    def delete(self, value):
        stat, node = self.find(value)
        if stat != 'found':
            return self
        _node = node
        if node[1] != None:
            node = node[1]
            while node[0] != None:
                node = node[0]
        _node.value = node.value
        _node = node
        while node.parent != None:
            if node.dire == 0:
                node.idx += 1
                node.parent.idx -= 1
        node = _node
        if node.color == red:
            node.parent[node.dir] = node[1]
            return self
        node.color = red if is_red(node[1]) else black
        while True:
            if is_red(node) or node.parent==None:
                node.color = black
                break
            if is_red(node.sibling()):
                node.sibling().color = black;
                node.parent.color = red;
                node.parent.rotate(node.dire)
            if is_red(node.sibling()[1-node.dire]):
                node.sibling().color = node.parent.color
                node.parent.color = black
                node.sibling()[1-node.dire].color = black
                node.parent.rotate(node.dire)
                break
            if is_red(node.sibling()[node.dire]):
                node.sibling()[node.dire].color = node.parent.color
                node.parent.color = black;

from random import random
node = rbnode(0, black)
for i in range(1,10):
    x = random()
    print (x)
    node = node.insert(x)
print (node.get(1).value)
